The security and authenticity of information transferred through data communication systems is of paramount importance. Much of the information is of a sensitive nature and lack of proper control may result in economic and personal loss. Cryptographic systems have been developed to address such concerns.
Public key cryptography permits the secure communication over a data communication system without the necessity to transfer identical keys to other parties in the information exchange through independent mechanisms, such as a courier or the like. Public key cryptography is based upon the generation of a key pair, one of which is private and the other public that are related by a one way mathematical function. The one way function is such that, in the underlying mathematical structure, the public key is readily computed from the private key but the private key cannot feasibly be ascertained from the public key.
One of the more robust one way functions involves exponentiation in a finite field where an integer k is used as a private key and the generator of the field α is exponentiated to provide a public key K=αk. Even though α and K are known, the underlying mathematical structure of the finite field makes it infeasible to obtain the private key k. Public key cryptography may be used between parties to establish a common key by both parties exchanging their public keys and exponentiating the other parties public key with their private key. Public key cryptography may also be used to digitally sign a message to authenticate the origin of the message. The author of the message signs the message using his private key and the authenticity of the message may then be verified using the corresponding public key.
The security of such systems is dependent to a large part on the underlying mathematical structure. The most commonly used structure for implementing discrete logarithm systems is a cyclic subgroup of a multiplicative group of a finite field in which the group operation is multiplication or cyclic subgroups of elliptic curve groups in which the group operation is addition.
An elliptic curve E is a set of points of the form (x, y) where x and y are in a field F, such as the integers modulo a prime p, commonly referred to as Fp, and x and y satisfy a non-singular cubic equation, which can take the form y2=x3+ax+b for some a and b in F. The elliptic curve E also includes a point at infinity, indicated as O. The points of E may be defined in such a way as to form a group. The point O is the identity of the group, so that O+P=P+O=P for any point P in E. For each point P, there is another point, which we will write as −P, such that P+(−P)=P+(−P)=O. For any three points P, Q, R in E, associativity holds, which means that P+(Q+R)=(P+Q)+R. Identity, negation and associativity are the three axiomatic properties defining a group. The elliptic curve group has the further property that it is abelian, meaning that P+Q=Q+P.
Scalar multiplication can be defined from addition as follows. For any point P and any positive integer d, dP is defined as P+P+ . . . +P, where d occurrences of P occur. Thus 1P=P and 2P=P+P, and 3P=P+P+P, and so on. We also define 0P=O and (−d) P=d (−P).
For simplicity, it is preferable to work with an elliptic curve that is cyclic (defined below) although in practice, sometimes a cyclic subgroup of the elliptic curve is used instead. Being cyclic means that there is a generator G, which is a point in the group such that every other point P in the group is a multiple of G, that is to say, P=dG, for some positive integer d. The smallest positive integer n such that nG=0 is the order of G (and of the curve E, when E is cyclic). In cryptographic applications, the elliptic curves are chosen so that n is prime.
In an elliptic curve cryptosystem, the analogue to exponentiation is point multiplication. Thus it is a private key is an integer k, the corresponding public key is the point kP, where P is a predefined point on the curve that is part of the system parameters. The seed point P will typically be the generator G. The key pair may be used with various cryptographic algorithms to establish common keys for encryption and to perform digital signatures. Such algorithms frequently require the verification of certain operations by comparing a pair of values as to confirm a defined relationship, referred to as the verification equality, between a set of values.
One such algorithm is the Elliptic Curve Digital Signature Algorithm (ECDSA) used to generate digital signatures on messages exchanged between entities. Entities using ECDSA have two roles, that of a signer and that of a verifier. A signer selects a long term private key d, which is an integer d between 1 and n−1 inclusive. The integer d must be secret, so it is generally preferable to choose d at random. The signer computes Q=dG. The point Q is the long-term public key of the signer, and is made available to the verifiers. Generally, the verifiers will have assurance generally by way of a certificate from a CA, that Q corresponds to the entity who is the signer. Finding the private key d from the public key Q is believed to an intractable problem for the choices of elliptic curves used today.
For any message M, the signer can create a signature, which is a pair of integers (r, s) in the case ECDSA. Any verifier can take the message M, the public key Q, and the signature (r, s), and verify whether it was created by the corresponding signer. This is because creation of a valid signature (r, s) is believed to possible only by an entity who knows the private key d corresponding to the public key Q.
The signing process is as follows. First, the signer chooses some integer k in the interval [1, n−1] that is to be used as a session, or ephemeral, private key. The value k must be secret, so generally it is preferable to choose k randomly. Then, the signer computes a point R=kG that has co-ordinates (x, y). Next, the signer converts x to an integer x′ and then computes r=x′ mod n, which is the first coordinate of the signature. The signer must also compute the integer e=h(M) mod n, where h is some hash function, generally one of the Secure Hash Algorithms (such as SHA-1 or SHA-256) defined in Federal Information Processing Standard (FIPS) 180-2. Finally, the second coordinate s is computed as s=(e+dr)/s mod n. The components (r, s) are used by the signer as the signature of the message, M, and sent with the message to the intended recipient.
The verifying process is as follows. First the verifier computes an integer e=h(M) mod n from the received message. Then the verifier computes integers u and v such that u=e/s mod n and v=r/s mod n. Next, the verifier computes a value corresponding to the point R that is obtained by adding uG+vQ. This has co-ordinates (x, y). Finally the verifier converts the field element x to an integer x′ and checks that r=x′ mod n. If it does the signature is verified.
From the above, the verification of an ECDSA signature appears to take twice as long as the creation of an ECDSA signature, because the verification process involves two scalar multiplications, namely uG and vQ, whereas signing involves only one scalar multiplication, namely kG. Elliptic curve scalar multiplications consume most of the time of these processes, so twice as many of them essentially doubles the computation time. Methods are known for computing uG+vQ that takes less time than computing uG and vG separately. Some of these methods are attributed to Shamir, some to Solinas, and some to various others. Generally, these methods mean that computing uG+vQ can take 1.5 times as long as computing kG.
Another commonly used method to accelerate elliptic curve computations is pre-computing tables of multiples of G. Such pre-computed tables save time, because the point G is generally a fixed system parameter that is re-used repeatedly. The simplest pre-compute table consists of all multiples 2^jG for j from 0 to t, where t is the bit-length of n. With such a pre-computed table, computing an arbitrary multiple kG can be done with an average of t/2 point additions or less. Roughly, this a threefold improvement over the basic method of computing kG, which clearly demonstrates the benefit of pre-computation. Generally speaking, larger pre-computed tables yield better time improvements. The memory needed to store the pre-computed tables has a significant cost. Therefore, implementers must balance the benefit of faster operations with the extra cost of larger tables. The exact balance generally depends of the relative importance of speed versus memory usage, which can vary from one implementation to another. Pre-computation can also be applied to the public key Q. Generally, the public key Q tends to vary more often than G: as it is different for each correspondent, whereas G is always fixed for a given system. Therefore the cost of one-time pre-computation for Q is amortized over a smaller number of repeated run-time computations involving Q. Nevertheless, if Q is to be used more than once, some net savings on time will be achieved. Public keys that are heavily used include those of certification authorities (CA), especially root, trusted or anchor CA public keys (that are pre-installed into a system). Therefore, pre-computation may be worthwhile for CA elliptic curve public keys where, for example, the protocol requires verification of a CA's certificate. Another difference between pre-computations of Q versus G is the cost of storing or communicating the pre-computed tables. Each public key Q requires its own pre-computed table. In a system with many distinct public keys, these costs may accumulate to the point that any benefit of faster computation is offset by the need to store or communicate keys. The net benefit depends on the relative cost of time, memory and bandwidth, which can vary tremendously between implementations and systems. Again, in the case of CA public keys, especially root, trusted or anchor CA keys, these keys tend to be fewer in number than end-entity public keys, so that the cost of pre-computation will generally be less and amortised over more operations.
Tables of multiples of points are not merely useful during pre-computation. In practice, such tables are commonly generated at run-time, during an initial phase of each computation. The savings provided by these tables is essentially that of avoiding certain repetitious operations that occur within a single computation. A single computation has less internal repetitions than two distinct computations have in common, so that saved repetition amount to less than pre-computation. Nevertheless, it has been found that with a judicious choice of table, the time need for a single computation can be reduced. The table takes time to compute, and computation of the table cannot be amortized over multiple computations, so is incurred for every computation. Experience has shown that particular tables decrease the amount of time needed because computing the table takes less time than the repetition operations that would have otherwise been needed. Usually, there is an optimum size and choice of table. Another cost of such tables is the memory needed to temporarily store the table. The cost of such memory may affect the optimal choice of table. Windowing methods are examples of such tables computed on the fly.
Not withstanding all of the above known techniques for efficient implementation, further efficiency improvements are desirable. In particular, the efficiency of verifying of ECDSA signatures is particularly desirable. Extensive pre-computation allows ECDSA signatures to be generated very quickly. In fact, ECDSA signature generation is one of the fastest digital signature generation algorithms known. On the other hand, ECDSA signature verification is relatively slower, and there are other signature algorithms have similar verification times to ECDSA. Improvement of ECDSA verification time is therefore important, especially for environments where verification time is a bottleneck. In general, there is a need to enhance the efficiency of performing a computation to verify that a value corresponds to the sum of two of the values. It is therefore an object of the present invention to obviate or mitigate the above disadvantages.